//
// Created by HP on 2022/3/8.
//

#ifndef FONTRENDER_FONTRASTER_H
#define FONTRENDER_FONTRASTER_H

#include "video.h"
#include "vertex.h"

// TODO 压缩 NET

// Scan-line 算法思想
// 多边形离散表示
// - 多边形可以由离散的顶点表示:
//         o ----- o
//          \       \
//           o       \
//           /        \
//          o -------- o
// 扫描过程
// - 扫描线从一端扫描到另一端: 如 沿 y 轴自下往上平行于 x 轴扫描
//   将扫描线与线段求交点, 再将交点按 x 轴坐标升序排列, 两两之间填充像素
//         o ----- o
//          \       \
//  -------- *=======* -----------
//           /========\
//          o -------- o
//
//           o      o
//          / \    / \           .
// ------- *===*--*===*--------------
//        /=====\/=====\
//       o==============o
// 求交点的优化
// - 线段的连贯性
//  -- o --> (x0, y0)
//  dy  \
//  ---- * --> (xi, yi)
//        \
//         o --> (x1, yi)
//  已知线段起点为 (x0, y0), 终点为 (x1, y1)
//  假如扫描线从 y0 处移动 dy 的距离, 而线段是连贯的,
//  意味着我们并不用再解一次方程来求下一个交点 (xi, yi)
//  而是可以通过如下方法求:
//  k = (y1 - y0) / (x1 - x0)
//  y0 = k * x0 + b
//  yi = k * xi + b
//  yi = y0 + dy
//  联立上面等式得:
//  dy = k * (xi - x0) 即:
//  dx = dy / k
//    where k = (y1 - y0) / (x1 - x0)
//  而 dy、y0、y1、x0、x1 都是已知量, 所以 dx 是一个常数。
// - 数据结构构想
//   -- 优化方向: 多边形有很多条边, 但求交点的时候, 扫描线只与部分边有交点
//   所以要利用合理的数据结构对多边形的边进行有效的表示和排列
//   -- 数据结构定义:
//   --- 边(线段)的定义:
//   我们要合理的表示一条边并利用线段的连贯性,
//   那么我们必须要知道:
//      1. 起点 x 值     o --> (x1, y1)    假如已知 x0, y1, dx
//      2. 终点 y 值      \                我们就可以计算出扫描线前进 dy 时 dx 的值,
//      3. dx -> 1/k      o --> (x0, y0)  也就知道下一个交点为 (x0 + dx, y + dy)
//                                        当 y + dy > y1 时整一个线段也就被扫描完毕了
//   所以一条边 Edge 就可以定义为:
//   struct Edge {
//       double x_sta;
//       double y_end;
//       double dx;
//   }
//   而每一个线段也可以被划分为 已扫描部分 或 未扫描部分:
//   |        /===/      已扫描
//   |       /===/
//   v  ----*---*------
//         /   /         未扫描
//   而已扫描的部分不用再处理, 于是我们可以在扫描的过程中更新 Edge 结构中的 x ,
//   从而更新新线段的状态, 而足够巧合的是:
//   更新后的 x 和扫描线所在的 y 刚好构成了新的交点 p 的坐标 (x, y)
//   --- NET(新边表) 和 AET(活动边表)
//   按照上面对线段的部分的划分, 我们已经有减少求交点运算的思路:
//      1. 将线段划分为 正在扫描 和 未扫描 两种
//      2. 在扫描的过程中更新线段的状态
//      3. 平行线在 y 方向上没有长度, 不用表示
//   按照这个思路, 我们来确定两个数据结构来表示 正在扫描 和 未扫描 两种线段
//   首先来确定一下我们需要的良好性质:
//      1. 边在 未扫描边表 中的排列顺序最好要按照 扫描线前进时遇到边的顺序 排列:
//                o   o            如左图所示:
//       ^      7/6\5/4\3          扫描线从下往上扫描, 所以我们期望
//       | ---- o - o - o -------  边在 未扫描边表 中的排列顺序为:
//       |     1 \     2 \          [o]->[1]->[2]
//       | ------ o ----- o -----   [^]
//                                  ...
//                                  [o]->[3]->[4]->[5]->[6]->[7]
//       我们发现:
//       - 有些边的起始位置是一样的, 这意味着扫描线在前进时会同时遇到几条新的线段
//         即: 未扫描边表 中有些线段应该并排在一起
//         所以每一个表项也应该是一个线性表 (可以是动态数组或链表)
//       - 为了让 未扫描边表 照着扫描线前进方向排序, 我们可以以空间换时间, 即:
//         为扫描线的每一个 y 值都开辟一个位置。 这样一来, 在扫描线前进时
//         将要遇到哪些线段就很容易得到
//      2. 边在 正在扫描边表 中的排列顺序要按照 x_sta 升序排列:
//              1  o  2    3  o  4
//         ---- o --- o -- o --- o ----
//             o ===== o  o ===== o
//        未扫描边表: [ 1 | 2 | 3 | 4 ]
//        这样一来我们可以在将 未扫描边表 中获取交点 pi (i = 1, 2, 3, 4)
//        并将交点两两匹配 (p1, p2), (p3, p4)
//        最后在匹配的点对之间填充像素即可
//              1  o  2    3  o  4
//         ---- o === o -- o === o ----
//             o ===== o  o ===== o
//   最后我们为了简洁描述将 未扫描边表 称为 NET(新边表), 将 正在扫描边表 称为 AET(活动边表)
//   在 C 语言中表示这两个结构: (我选择以链表形式表示并列的边)
//   typedef struct Edge {
//    double xi;    // 扫描线与线段交点的 x 轴坐标
//    double ki;    // ki = 1 / 线段的斜率 k
//    double y_max; // 线段的 y 轴最大值
//    struct Edge *next;
//   } Edge;
//   Edge* NET[N];
//   Edge* AET;
//   --- 算法总体思路:
//   在推导出上面的数据结构后, 我们总结一下算法的思路:
//    0. 前提
//    - 拥有一个多边形的顶点列表
//    - 该顶点列表要按照顺指针或逆时针方向储存顶点
//              o ------> o
//              ^         |
//              |         v
//              o <------ o
//      只有这样排列顶点, 顶点列表中相邻的点才一定是多边形的一条边
//    1. 根据输入顶点列表建立 初始NET:
//       1.1 确定 N :
//           N = 扫描线扫描范围
//             = y_max - y_min + 1 (y_min 顶点中最大的 y, y_min 同理)
//       1.2 根据点对确定线段表示:
//           假设在顶点列表中取出点对 (x0, y0)、(x1, y1)
//           假设扫描线每次前进 1 像素, 即: dy = 1
//           计算出 k = (y1 - y0) / (x1 - x0)
//                dx = dy / k = 1 / k
//                x_sta = min(x0, x1)
//                y_end = max(y0, y1)
//                y_sta = min(y0, y1)
//           并将该边放入 NET[y_sta - y_min] 中
//       1.3 重复上述过程直到遍历完顶点列表
//    2. 初始扫描线 y_scan = y_min;
//       初始化 AET , Edge* AET = malloc(sizeof(Edge));
//       AET 有一个头结点方便插入
//    3. 绘制:
//       3.1 将 NET[y_scan - y_min] 中所有的元素加入 AET 中
//       3.2 将 AET 中的元素按 x_sta 升序排列
//       3.3 两两匹配点对 (pi, pj), 并填充平行线 pi-pj
//       3.4 更新 AET 中边的状态: edge.x_sta = edge.x_sta + dx
//       3.5 删除边: 如果扫描线已经将线段扫描完毕, 则将该边从 AET 中删除
//                即: if y_scan > edge.y_end then delete edge
//       1.6 重复上述过程直至 AET 表为空
//    4. 算法结束
//        但细心的读者可能会发现这样一种情况:
//        ^      4
//       4|  o ------- o
//       3|  1\       /3
//  -----2|--- *-.   * -----
//       1|   a  2`-o b
//      --+----------------->
//        |  1 2  3  4 5
//     当扫描线扫描到如图所示位置时,
//     交点 '*' a 其实是线段 1 的起点, 以及线段 2 的终点
//     所以此时 AET 中有三个元素(奇数个元素) [l1]->[l2]->[l3] 所以无法两两配对
//     所以我们有多种解决方案:
//        1. 在两两配对时, 若配对失败, 则从第二个元素开始重新配对
//        2. 维护一个 cnt 变量记录 AET 中元素的数量, 若 cnt 为奇数时, 则从第二个元素开始配对

typedef struct {
    Vertex *vertices;
    int size;
} Glyph;

// 边(线段)
typedef struct Edge {
    double x_sta; // 起点坐标的 x
    int y_end;    // 终点坐标的 y
    double dx;    // 扫描线移动 dy 时, x 的增量
    struct Edge *next;
} Edge;

/**
 * Scan-Line 算法实现
 * @param glyphs 封闭多边形的集合
 * @param size  glyphs 的长度
 */
void scanLine(Glyph *glyphs, int size);

/**
 * 用于初始化 NET 表, NET 表在传入前要开辟好空间
 * @param glyph 按照顺时针或逆时针方向排列的封闭多边形的顶点集合
 * @param NET y_max - y_min 个表项
 * @param y_min
 */
void initNET(Glyph glyph, Edge* *NET, int y_min);

#endif //FONTRENDER_FONTRASTER_H
